#include <iostream>
using namespace std;

struct TreeNode {
int val;
       TreeNode *left;
       TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* SubFlatten(TreeNode *root);
void flatten(TreeNode *root) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    if(!root)
        return;
    SubFlatten(root);
}

TreeNode* SubFlatten(TreeNode *root){
    TreeNode *leftIP = NULL;
    TreeNode *rightIP = NULL;
    
    if(root->left){
        leftIP = SubFlatten(root->left);
    }
    if(root->right){
        rightIP = SubFlatten(root->right);
    }
    if(root->left){
        leftIP->right = root->right;
        root->right = root->left;
        root->left = NULL;
        if(leftIP->right){
            return rightIP;
        }
        else{
            return leftIP;
        }
    }
    if(root->right){
        return rightIP;
    }
    return root;
}

int main(){
    return 0;
}